package codingforgreat.class52;

import java.util.LinkedList;
import java.util.Queue;

/**
 * N 个灯泡排成一行，编号从 1 到 N 。最初，所有灯泡都关闭。每天只打开一个灯泡，直到 N 天后所有灯泡都打开。
 * 给你一个长度为 N 的灯泡数组 blubs ，其中 bulls[i] = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。
 * 给你一个整数 K ，请你输出在第几天恰好有两个打开的灯泡，使得它们中间 正好 有 K 个灯泡且这些灯泡 全部是关闭的 。
 * 如果不存在这种情况，返回 -1 。如果有多天都出现这种情况，请返回 最小的天数 。
 * */
public class Problem_0683_KEmptySlots {
    public static int kEmptySlots1(int[] bulbs, int k) {
        int n = bulbs.length;
        int[] days = new int[n];
        for(int i = 0;i < n;i++){
            days[bulbs[i] - 1] = i + 1;
        }
        int ans = Integer.MAX_VALUE;
        if(k == 0){
            for(int i = 1;i < n;i++){
                ans = Math.min(ans,Math.max(days[i - 1], days[i]));
            }
        }else{
            LinkedList<Integer> queue = new LinkedList<>();
            for(int i = 1;i < n && i < k;i++){
                while (!queue.isEmpty() && days[queue.peek()] >= days[i]){
                    queue.poll();
                }
                queue.offer(i);
            }
            for(int i = 1,j = k;j < n - 1;i++,j++){
                while (!queue.isEmpty() && days[queue.peek()] >= days[j]){
                    queue.poll();
                }
                queue.offer(j);
                int cur = Math.max(days[i - 1],days[j - 1]);
                if(!queue.isEmpty()){
                    if (days[queue.peekFirst()] > cur) {
                        ans = Math.min(ans, cur);
                    }
                    if (i == queue.peekFirst()) {
                        queue.pollLast();
                    }
                }

            }

        }
        return (ans == Integer.MAX_VALUE) ? -1 : ans;
    }
}
